#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    int numDistinct(string s, string t) {
        //dp[i][j] 表示在t 0~i s 0~j
        //通过结尾是否包含s[j]t[i]推到状态转移方程
        vector<vector<int>>dp(t.size(),vector<int>(s.size(),0));
        dp[0][0]=s[0]==t[0];
        for(int j=1;j<s.size();j++){
            dp[0][j]=dp[0][j-1];
            if(t[0]==s[j])dp[0][j]+=1;
        }
        for(int i=1;i<t.size();i++){
            for(int j=i;j<s.size();j++){
                dp[i][j]+=dp[i][j-1];
                if(t[i]==s[j])dp[i][j]+=dp[i-1][j-1];
                dp[i][j]%=(long long)1e9+7;
            }
        }
        return dp[t.size()-1][s.size()-1];
    }
};